#pragma once

#include <cstdint>
#include <functional>
#include <algorithm>
#include <stdexcept>
#include "allocator.hh"

namespace kratos { namespace corelib {

// Scene grid
template <typename T>
class NineGrid {
    struct Item {
        T t;
        int32_t x;
        int32_t y;
        bool operator==(T t1) {
            return (t == t1);
        }
    };
    using GridFunc = std::function<void(T, T)>;
    using ActorList = std::list<Item>;
    ActorList actorList_; // Actor list
    std::int32_t row_; // row index in scene
    std::int32_t col_; // column index in scene

public:
    // ctor
    // @param row row index
    // @param col column index
    NineGrid(std::int32_t row, std::int32_t col) {
        row_ = row;
        col_ = col;
    }
    // Returns row index
    std::int32_t getRow() {
        return row_;
    }
    // Returns column index
    std::int32_t getCol() {
        return col_;
    }
    // Notify observer and t
    // @param t message source
    // @param func callback function
    void notify(T t, GridFunc func) {
        for (auto actor : actorList_) {
            if (func) {
                func(t, actor.t);
                func(actor.t, t);
            }
        }
    }
    // Notify ONLY observer
    // @param t message source
    // @param func callback function
    void notifyOthers(T t, GridFunc func) {
        for (auto actor : actorList_) {
            if (actor.t != t) {
                if (func) {
                    func(t, actor.t);
                }
            }
        }
    }
    // Enter grid
    // @param t new camer
    void enter(T t, int32_t x, int32_t y) {
        actorList_.push_back(Item{ t, x, y });
    }
    // Leave grid
    // @param t the one need to leave
    void leave(T t) {
        auto it = std::find(actorList_.begin(), actorList_.end(), t);
        if (it == actorList_.end()) {
            return;
        }
        actorList_.erase(it);
    }

    const std::list<Item>& getActors() const {
        return actorList_;
    }
};

// Nine grid scene
//
//  -----> X-axis 
//  |
//  |
// \/
// Y-axis
//
template <typename T>
class NineGridScene {
    using GridFunc = std::function<void(T, T)>;
    using QueryFunc = std::function<bool(T, std::int32_t, std::int32_t, std::int32_t)>;
    std::int32_t gridSize_; // grid size
    std::int32_t xrange_; // X-axis range
    std::int32_t yrange_; // Y-axis range
    std::int32_t row_; // total row in scene
    std::int32_t col_; // total column in scene
    using GridNeighbor = std::vector<NineGrid<T>*>;
    using GridWorld = std::vector<std::vector<NineGrid<T>*>>;
    GridWorld gridWorld_; // 2D Grid world
    GridNeighbor gridNeighbor_;
    GridNeighbor srcNeighbor_;
    GridNeighbor dstNeighbor_;
    using QueryResult = std::list<T>;
    QueryResult queryResult_; // Query result

public:
    // ctor
    // @param gridSize Grid size
    // @param xrange X-axis range
    // @param yrange Y-axis range
    NineGridScene(std::int32_t gridSize, std::int32_t xrange, std::int32_t yrange) {
        gridSize_ = 0;
        xrange_ = 0;
        yrange_ = 0;
        row_ = 0;
        col_ = 0;
        start(gridSize, xrange, yrange);
    }
    // dtor
    ~NineGridScene() {
        for (auto& v : gridWorld_) {
            for (auto grid : v) {
                delete grid;
            }
        }
    }
    // Enter scene
    // @param t The new camer
    // @param x X-coordinate
    // @param y Y-coordinate
    // @param enterAOI callback function
    // @retval true
    // @retval false
    bool enter(T t, std::int32_t x, std::int32_t y, GridFunc enterAOI) {
        auto nineGrid = getGrid(x, y);
        nineGrid->notify(t, enterAOI);
        auto& neighbor = getNeighbor(x, y);
        for (auto grid : neighbor) {
            grid->notify(t, enterAOI);
        }
        nineGrid->enter(t, x, y);
        return true;
    }
    // Enter scene but not owner
    // @param t The new camer
    // @param x X-coordinate
    // @param y Y-coordinate
    // @param enterAOI callback function
    // @retval true
    // @retval false
    bool otherEnter(T t, std::int32_t x, std::int32_t y, GridFunc enterAOI) {
        auto nineGrid = getGrid(x, y);
        nineGrid->notify(t, enterAOI);
        auto& neighbor = getNeighbor(x, y);
        for (auto grid : neighbor) {
            grid->notify(t, enterAOI);
        }
        return true;
    }
    // Leave scene
    // @param t The one need to leave
    // @param x X-coordinate
    // @param y Y-coordinate
    // @param leaveAOI callback function
    // @retval true
    // @retval false
    bool leave(T t, std::int32_t x, std::int32_t y, GridFunc leaveAOI) {
        auto nineGrid = getGrid(x, y);
        nineGrid->notifyOthers(t, leaveAOI);
        auto& neighbor = getNeighbor(x, y);
        for (auto grid : neighbor) {
            grid->notifyOthers(t, leaveAOI);
        }
        nineGrid->leave(t);
        return true;
    }
    // Leave scene but not owner
    // @param t The one need to leave
    // @param x X-coordinate
    // @param y Y-coordinate
    // @param leaveAOI callback function
    // @retval true
    // @retval false
    bool otherLeave(T t, std::int32_t x, std::int32_t y, GridFunc leaveAOI) {
        auto nineGrid = getGrid(x, y);
        nineGrid->notify(t, leaveAOI);
        auto& neighbor = getNeighbor(x, y);
        for (auto grid : neighbor) {
            grid->notifyOthers(t, leaveAOI);
        }
        return true;
    }
    // Move in scene
    // @param t The one need to move
    // @param x0 old X-coordinate
    // @param y0 old Y-coordinate
    // @param x1 new X-coordinate
    // @param y1 new Y-coordinate
    // @param enterAOI callback function for entering notification
    // @param leaveAOI callback function for leaving notification
    // @param moveAOI callback function for moving notification
    // @retval true
    // @retval false
    bool move(T t, std::int32_t x0, std::int32_t y0, std::int32_t x1, std::int32_t y1, GridFunc enterAOI = nullptr,
        GridFunc leaveAOI = nullptr, GridFunc moveAOI = nullptr) {
        auto srcGrid = getGrid(x0, y0);
        auto dstGrid = getGrid(x1, y1);
        if (srcGrid == dstGrid) {
            srcGrid->notifyOthers(t, moveAOI);
            return true;
        }
        auto& srcNeighbor = getNeighbor(x0, y0, srcNeighbor_);
        auto& dstNeighbor = getNeighbor(x1, y1, dstNeighbor_);
        for (auto neighbor : srcNeighbor) {
            if (!isNeighbor(dstGrid, neighbor)) {
                // leave
                neighbor->notify(t, leaveAOI);
                neighbor->leave(t);
            } else {
                // move
                // TODO notifying frequency by distance
                neighbor->notifyOthers(t, moveAOI);
            }
        }
        for (auto neighbor : dstNeighbor) {
            if (!isNeighbor(srcGrid, neighbor)) {
                // enter
                neighbor->notify(t, enterAOI);
                neighbor->enter(t, x1, y1);
            }
        }
        return true;
    }

    const std::list<T>& queryCircle(T t, std::int32_t x, std::int32_t y,
        std::int32_t radius, QueryFunc queryFunc) {
        queryResult_.clear();
        gridNeighbor_.clear();
        auto srcGrid = getGrid(x, y);
        gridNeighbor_.push_back(srcGrid);
        if (!contain(srcGrid, x, y, radius)) {
            srcNeighbor_.clear();
            dstNeighbor_.clear();
            getNeighbor(x, y, srcNeighbor_);
            for (auto grid : srcNeighbor_) {
                if (overlap(grid, x, y, radius)) {
                    dstNeighbor_.push_back(grid);
                }
            }
        }
        if (queryFunc) {
            for (auto grid : dstNeighbor_) {
                for (auto actor : grid->getActors()) {
                    if (queryFunc(actor.t, x, y, radius)) {
                        queryResult_.push_back(actor.t);
                    }
                }
            }
        }
        return queryResult_;
    }

private:
    bool contain(NineGrid<T>* grid, std::int32_t x, std::int32_t y, std::int32_t radius) {
        auto x0 = grid->getRow() * gridSize_;
        auto x1 = x0 + gridSize_;
        auto y0 = grid->getCol() * gridSize_;
        auto y1 = y0 + gridSize_;
        return (((x - radius) > x0) && ((x + radius) < x1) && ((y - radius) > y0) && ((y + radius) < y1));
    }

    std::int32_t absolute(std::int32_t v) {
        return (v > 0 ? v : -1 * v);
    }

    bool overlap(NineGrid<T>* grid, std::int32_t x, std::int32_t y, std::int32_t radius) {
        auto x0 = grid->getRow() * gridSize_;
        auto x1 = x0 + gridSize_;
        auto y0 = grid->getCol() * gridSize_;
        auto y1 = y0 + gridSize_;
        auto cx0 = x - radius;
        auto cx1 = x + radius;
        auto cy0 = y - radius;
        auto cy1 = y + radius;
        int zx = absolute(x0 + x1 - cx0 - cx1);
        int gapx  = absolute(x0 - x1) + absolute(cx0 - cx1);
        int zy = absolute(y0 + y1 - cy0 - cy1);
        int gapy  = absolute(y0 - y1) + absolute(cy0 - cy1);
        return (zx <= gapx && zy <= gapy);
    }

    void start(std::int32_t gridSize, std::int32_t xrange, std::int32_t yrange) {
        gridSize_ = gridSize;
        xrange_ = xrange;
        yrange_ = yrange;
        if (gridSize > xrange || gridSize > yrange) {
            throw std::runtime_error("Invalid argument");
        }
        auto row = static_cast<std::int32_t>(xrange / gridSize);
        auto col = static_cast<std::int32_t>(yrange / gridSize);
        row_ = row;
        col_ = col;
        for (auto i = 0; i < row; i++) {
            gridWorld_.push_back(std::vector<NineGrid<T>*>(col, nullptr));
            for (auto j = 0; j < col; j++) {
                gridWorld_[i][j] = new NineGrid<T>(i, j);
            }
        }
        gridNeighbor_.assign(9, nullptr);
        srcNeighbor_.assign(9, nullptr);
        dstNeighbor_.assign(9, nullptr);
    }

    bool isNeighbor(NineGrid<T>* src, NineGrid<T>* dst) {
        auto maxRow = src->getRow() > dst->getRow() ? src->getRow() : dst->getRow();
        auto minRow = src->getRow() > dst->getRow() ? dst->getRow() : src->getRow();
        auto maxCol = src->getCol() > dst->getCol() ? src->getCol() : dst->getCol();
        auto minCol = src->getCol() > dst->getCol() ? dst->getCol() : src->getCol();
        return ((maxRow - minRow <= 1) && (maxCol - minCol <= 1));
    }    

    NineGrid<T>* getGrid(std::int32_t x, std::int32_t y) {
        if (x > xrange_) {
            x = xrange_;
        }
        if (y > yrange_) {
            y = yrange_;
        }
        auto row = static_cast<std::int32_t>(x / gridSize_);
        auto col = static_cast<std::int32_t>(y / gridSize_);
        return gridWorld_[row][col];
    }

    bool isValid(std::int32_t row, std::int32_t col) {
        if (row < 0 || row >= row_) {
            return false;
        }
        if (col < 0 || col >= col_) {
            return false;
        }
        return true;
    }

    const GridNeighbor& getNeighbor(std::int32_t x, std::int32_t y, GridNeighbor& neighbor) {
        auto row = static_cast<std::int32_t>(x / gridSize_);
        auto col = static_cast<std::int32_t>(y / gridSize_);
        neighbor.clear();
        if (isValid(row - 1, col - 1)) {
            neighbor.push_back(gridWorld_[row - 1][col - 1]);
        }
        if (isValid(row - 1, col)) {
            neighbor.push_back(gridWorld_[row - 1][col]);
        }
        if (isValid(row - 1, col + 1)) {
            neighbor.push_back(gridWorld_[row - 1][col + 1]);
        }
        if (isValid(row, col - 1)) {
            neighbor.push_back(gridWorld_[row][col - 1]);
        }
        if (isValid(row, col + 1)) {
            neighbor.push_back(gridWorld_[row][col + 1]);
        }
        if (isValid(row + 1, col - 1)) {
            neighbor.push_back(gridWorld_[row + 1][col - 1]);
        }
        if (isValid(row + 1, col)) {
            neighbor.push_back(gridWorld_[row + 1][col]);
        }
        if (isValid(row + 1, col + 1)) {
            neighbor.push_back(gridWorld_[row + 1][col + 1]);
        }
        return neighbor;
    }

    const GridNeighbor& getNeighbor(std::int32_t x, std::int32_t y) {
        return getNeighbor(x, y, gridNeighbor_);
    }
};

}}
